package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 17:47 2020/8/8
 * @Description
 * 给定一棵二叉树，你需要计算它的直径长度
 * 一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 *         1
         / \
        2   3
       / \
      4   5
    返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]
    *
 * */

public class DiameterOfBinaryTree {

    /**
     * 要想直径最长也就是一个节点的左深度+右深度+1最大（不一定必须过根节点）
     *
     * @param root
     * @return
     */
    int ans = 1;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        depth(root);
        //此处-1是因为题目中规范的
        return ans - 1;
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        // leftDepth+rightDepth+1 就是直径长度
        ans = Math.max(ans, (leftDepth + rightDepth + 1));
        return Math.max(leftDepth, rightDepth) + 1;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
